import { TrieNode } from './model'

class Trie {
  constructor () {
    this._root = new TrieNode()
    this._size = 0
  }

  getSize () {
    return this._size
  }

  add (word) {
    let cur = this._root
    for (let i = 0; i < word.length; i++) {
      const character = word.charAt(i)
      if (!cur.next.get(character)) {
        cur.next.set(character, new TrieNode())
      }
      cur = cur.next.get(character)
    }
    if (!cur.isWord) {
      cur.isWord = true
      this._size++
    }
  }

  // 包含某个单词
  contains (word) {
    let cur = this._root
    for (let i = 0; i < word.length; i++) {
      const character = word.charAt(i)
      if (!cur.next.get(character)) {
        return false
      }
      cur = cur.next.get(character)
    }
    return cur.isWord
  }

  // 包含某个前缀
  startsWith (prefix) {
    let cur = this._root
    for (let i = 0; i < prefix.length; i++) {
      const character = prefix.charAt(i)
      if (!cur.next.get(character)) {
        return false
      }
      cur = cur.next.get(character)
    }
    return true
  }

  // 模式匹配, '.'表示一个任意字符(通配符）
  search (word) {
    return this._match(this._root, word, 0)
  }

  _match (node, word, index) {
    if (index === word.length) {
      return node.isWord
    }
    const character = word.charAt(index)
    // 如果不是一个'.'
    if (character !== '.') {
      if (!node.next.get(character)) {
        return false
      }
      return this._match(node.next.get(character), word, index + 1)
    } else {
      // 如果是'.'模糊匹配
      for (const c of node.next.keys()) {
        if (this._match(node.next.get(c), word, index + 1)) {
          return true
        }
      }
      return false
    }
  }
}

export default Trie
